/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function (k, nums) {
  this.data = new MinHeap()
  this.k = k
  nums.forEach((num) => this.add(num))
}

/**
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function (val) {
  this.data.push(val)

  if (this.k < this.data.size()) {
    this.data.pop()
  }
  return this.data.peek()
}

// 最小堆
class MinHeap {
  constructor() {
    this.heap = []
  }
  size() {
    return this.heap.length
  }

  peek() {
    if (this.size()) {
      return this.heap[0]
    }
    return null
  }
  /* 
  添加的时候,向后面添加,向上面移动

*/
  push(node) {
    this.heap.push(node)
    // 将node传入主要是为了后面继承的改写罢了,万一node是一个对象呢?我们只需要使用node节点的某一个字段进行比较,抽出compare函数也是一样的道理,后面继承的时候直接改写compare函数就可以了
    this.shiftUp(node, this.size() - 1)
  }

  /* 
    删除节点
    使用最后一个节点替换掉第一个节点,然后向下移动
  */
  pop() {
    if (!this.size()) {
      return null
    }
    if (this.size() === 1) {
      return this.heap.pop()
    }
    let lastNode = this.heap.pop()
    this.heap[0] = lastNode
    this.shiftDown(this.heap[0], 0)
  }
  // 比较函数
  compare(a, b) {
    return a - b < 0
  }
  // 变量交换
  swap(idx, parentIdx) {
    ;[this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]]
  }
  // 向上移动
  shiftUp(node, idx) {
    let parentIdx = (idx - 1) >> 1
    while (idx > 0) {
      if (this.compare(node, this.heap[parentIdx])) {
        this.swap(idx, parentIdx)
        idx = parentIdx
        parentIdx = (idx - 1) >> 1
      } else {
        break
      }
    }
  }
  // 向下移动
  shiftDown(node, idx) {
    while (idx < this.size() - 1) {
      let leftIdx = (idx + 1) * 2 - 1
      let rightIdx = leftIdx + 1
      // 左子节点肯定有,右子节点未必有
      if (this.compare(this.heap[leftIdx], node)) {
        // 左子节点小于父节点
        if (typeof this.heap[rightIdx] !== 'undefined' && this.compare(this.heap[rightIdx], this.heap[leftIdx])) {
          // 右子节点存在并且小于左子节点
          this.swap(rightIdx, idx)
          idx = rightIdx
        } else {
          this.swap(leftIdx, idx)
          idx = leftIdx
        }
      } else if (typeof this.heap[rightIdx] !== 'undefined' && this.compare(this.heap[rightIdx], node)) {
        // 右子节点存在并且小于父节点
        this.swap(rightIdx, idx)
        idx = rightIdx
      } else {
        break
      }
    }
  }
}

// let a = new MinHeap();
// a.push(3);
// a.push(3);
// a.push(9);
// a.push(5);
// a.push(2);
// a.push(4);
// a.push(1)
// a.pop()
// a.pop()
// a.pop()
// a.pop()
// console.log(a);

let kthLargest = new KthLargest(2, [0])
kthLargest.add(-1) // return 4
kthLargest.add(1) // return 5
kthLargest.add(-2) // return 5
kthLargest.add(-4) // return 8
kthLargest.add(3) // return 8

console.log(kthLargest)
console.log(NaN < 0)
